package com.example.lettcode._202411._20241119;

/*
463. 岛屿的周长
给定一个 row x col 的二维网格地图 grid ，其中：grid[i][j] = 1 表示陆地， grid[i][j] = 0 表示水域。
网格中的格子 水平和垂直 方向相连（对角线方向不相连）。整个网格被水完全包围，但其中恰好有一个岛屿（或者说，一个或多个表示陆地的格子相连组成的岛屿）。
岛屿中没有“湖”（“湖” 指水域在岛屿内部且不和岛屿周围的水相连）。格子是边长为 1 的正方形。网格为长方形，且宽度和高度均不超过 100 。计算这个岛屿的周长。

示例 1：
输入：grid = [[0,1,0,0],[1,1,1,0],[0,1,0,0],[1,1,0,0]]
输出：16
解释：它的周长是上面图片中的 16 个黄色的边

示例 2：
输入：grid = [[1]]
输出：4

示例 3：
输入：grid = [[1,0]]
输出：4
 */
public class _02_dao_yu_de_zhou_chang {

    public static void main(String[] args) {
        int[][] grid = {{0,1,0,0}, {1,1,1,0}, {0,1,0,0}, {1,1,0,0}};
        System.out.println(islandPerimeter2(grid));
    }

    public static int islandPerimeter(int[][] grid) {
        int ret = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                // 格子的值
                int item = grid[i][j];
                if (item == 0) {
                    // 冰块则不做处理
                    continue;
                }

                if (i != 0) {
                    // 不是第一行，则判断上一个格子是冰块还是陆地，冰块，则周长+1，陆地，则周长不变
                    ret += grid[i-1][j] == 0 ? 1 : 0;
                } else {
                    // 是第一行，周长+1，因为肯定是陆地，而其上方不存在陆地，周长肯定+1
                    ret += 1;
                }

                if (j != 0) {
                    // 不是第一列，则判断左边格子是冰块还是陆地，冰块，则周长+1，陆地，则周长不变
                    ret += grid[i][j-1] == 0 ? 1 : 0;
                } else {
                    // 是第一列，周长+1，因为肯定是陆地，而其走边不存在陆地，周长肯定+1
                    ret += 1;
                }

                if (i != grid.length - 1) {
                    // 不是最后一行，则判断下方格子是冰块还是陆地，冰块，则周长+1，陆地，则周长不变
                    ret += grid[i+1][j] == 0 ? 1 : 0;
                }else {
                    // 是最后一行，周长+1，因为肯定是陆地，而其下方不存在陆地，周长肯定+1
                    ret += 1;
                }

                if (j != grid[i].length - 1) {
                    // 不是最后一列，则判断右边格子是冰块还是陆地，冰块，则周长+1，陆地，则周长不变
                    ret += grid[i][j+1] == 0 ? 1 : 0;
                }else {
                    // 是最后一列，周长+1，因为肯定是陆地，而其右方不存在陆地，周长肯定+1
                    ret += 1;
                }
            }
        }
        return ret;
    }


    public static int islandPerimeter2(int[][] grid) {
        int ret = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    // 一上来周长就加4条边的长度
                    ret += 4;
                    if (i > 0) {
                        // 非第一行，如果上面有陆地，则需要减去 2被边长，因为两块陆地边重合时，需要减去2被边长
                        ret -= grid[i-1][j] * 2;
                    }

                    if (j > 0) {
                        // 同理，左边有重叠，则减去两倍变成， 因为 遍历是从左到右，从上到下，所有只左边和上面需要统计
                        ret -= grid[i][j-1] * 2;
                    }
                }
            }
        }
        return ret;
    }
}
